<?php
/*
剑指 Offer 41. 数据流中的中位数
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
示例 1：

输入：
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]
示例 2：

输入：
["MedianFinder","addNum","findMedian","addNum","findMedian"]
[[],[2],[],[3],[]]
输出：[null,null,2.00000,null,2.50000]


限制：

最多会对 addNum、findMedian 进行 50000 次调用。



难度：困难

https://leetcode.cn/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/


*/

$obj = new Code_Offer41();
$res = $obj->main();

class Code_Offer41
{

    public function main()
    {
        $obj = new MedianFinder();
        $obj->addNum(1);
//        $obj->addNum(2);
        echo $obj->findMedian() . PHP_EOL;
//        $obj->addNum(3);
//        echo $obj->findMedian() . PHP_EOL;

    }
}

/*
 * 思路：
 * 建立一个大根堆，一个小根堆。
 * 如果对数据流进行排序，排序结果的前一半在大根堆，后一半在小根堆。那么中位数就可以直接靠堆顶两个数字获得
 * 注意点：
 * 1、第一个数默认放到大根堆里
 * 2、之后每次从流中获取新数据时，如果<=大根堆的堆顶，放入大根堆；>=大根堆的堆顶就放入小根堆
 * 3、新数据放入某个堆后都需要保证两个堆中的数量差值不能大于1，如果数量差大于1，匀一个到另一个堆里即可
 */
class MedianFinder
{
    private $maxHeap;
    private $minHeap;

    /**
     * initialize your data structure here.
     */
    function __construct()
    {
        $this->maxHeap = new SplMaxHeap();
        $this->minHeap = new SplMinHeap();
    }

    /**
     * @param Integer $num
     * @return NULL
     */
    function addNum($num)
    {
        // 注意点1
        if ($this->maxHeap->isEmpty()) {
            $this->maxHeap->insert($num);
            return;
        }
        // 注意点2
        if ($num <= $this->maxHeap->top()) {
            $this->maxHeap->insert($num);
        } else {
            $this->minHeap->insert($num);
        }
        // 注意点3
        if ($this->maxHeap->count() == $this->minHeap->count() + 2) {
            $this->minHeap->insert($this->maxHeap->extract());
        }
        if ($this->minHeap->count() == $this->maxHeap->count() + 2) {
            $this->maxHeap->insert($this->minHeap->extract());
        }
    }

    /**
     * @return Float
     */
    function findMedian()
    {
        $minSize = $this->minHeap->count();
        $maxSize = $this->maxHeap->count();

        $minHeapHead = $minSize > 0 ? $this->minHeap->top() : 0;
        $maxHeapHead = $maxSize > 0 ? $this->maxHeap->top() : 0;
        if ((($minSize + $maxSize) & 1) == 0) {
            return floatval(($minHeapHead + $maxHeapHead) / 2);
        }
        return $maxSize > $minSize ? $maxHeapHead : $minHeapHead;
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * $obj = MedianFinder();
 * $obj->addNum($num);
 * $ret_2 = $obj->findMedian();
 */